public class MinWindow {
    public String minWindow(String s, String t) {
        int len1 = s.length(), len2 = t.length();
        int[] hash1 = new int[58];
        int[] hash2 = new int[58];
        int type1 = 0, type2 = 0;
        int leftIndex = -1, rightIndex = -1;
        int length = 0, minLength = 0x3f3f3f3f;
        for (char c : t.toCharArray()) {
            if (hash2[c-'A']++ == 0) type2++;
        }
        int left = 0, right = 0;
        while (right < len1) {
            // 进窗口
            while (right < len1 && type1 < type2) {
                char c = s.charAt(right++);
                if (++hash1[c-'A'] == hash2[c-'A']) type1++;
            }
            // 出窗口,并且在出窗口的时候更新结果
            while (left < right && type1 == type2) {
                // 更新结果
                if (right - left < minLength) {
                    minLength = right - left;
                    leftIndex = left;
                    rightIndex = right;
                }
                char c = s.charAt(left++);
                if (hash1[c-'A']-- == hash2[c-'A']) type1--;
            }
        }
        return leftIndex == -1 ? "" : s.substring(leftIndex, rightIndex);
    }

    public static void main(String[] args) {
        MinWindow minWindow = new MinWindow();
        System.out.println(minWindow.minWindow("ADOBECODEBANC", "ABC"));
    }
}
